home *** CD-ROM | disk | FTP | other *** search
/ Atari Mega Archive 1 / Atari Mega Archive - Volume 1.iso / archiver / arc.zoo / arcsq.c < prev    next >
C/C++ Source or Header  |  1988-11-16  |  15KB  |  549 lines
  1. /*
  2.  * $Header: arcsq.c,v 1.3 88/07/31 18:53:32 hyc Exp $
  3.  */
  4.  
  5. /*
  6.  * ARC - Archive utility - ARCSQ 
  7.  *
  8.  * Version 3.10, created on 01/30/86 at 20:10:46
  9.  *
  10.  * (C) COPYRIGHT 1985 by System Enhancement Associates; ALL RIGHTS RESERVED 
  11.  *
  12.  * By:  Thom Henderson 
  13.  *
  14.  * Description: This file contains the routines used to squeeze a file when
  15.  * placing it in an archive. 
  16.  *
  17.  * Language: Computer Innovations Optimizing C86 
  18.  *
  19.  * Programming notes: Most of the routines used for the Huffman squeezing
  20.  * algorithm were lifted from the SQ program by Dick Greenlaw, as adapted to
  21.  * CI-C86 by Robert J. Beilstein. 
  22.  */
  23. #include <stdio.h>
  24. #include "arc.h"
  25.  
  26. /* stuff for Huffman squeezing */
  27.  
  28. #define TRUE 1
  29. #define FALSE 0
  30. #define ERROR (-1)
  31. #define SPEOF 256        /* special endfile token */
  32. #define NOCHILD (-1)        /* marks end of path through tree */
  33. #define NUMVALS 257        /* 256 data values plus SPEOF */
  34. #define NUMNODES (NUMVALS+NUMVALS-1)    /* number of nodes */
  35. #define MAXCOUNT (unsigned short) 65535    /* biggest unsigned integer */
  36.  
  37. /*
  38.  * The following array of structures are the nodes of the binary trees. The
  39.  * first NUMVALS nodes become the leaves of the final tree and represent the
  40.  * values of the data bytes being encoded and the special endfile, SPEOF. The
  41.  * remaining nodes become the internal nodes of the final tree. 
  42.  */
  43.  
  44. struct nd {            /* shared by unsqueezer */
  45.     unsigned short    weight;    /* number of appearances */
  46.     short        tdepth;    /* length on longest path in tree */
  47.     short        lchild, rchild;    /* indices to next level */
  48. }               node[NUMNODES];    /* use large buffer */
  49.  
  50. static int      dctreehd;    /* index to head of final tree */
  51.  
  52. /*
  53.  * This is the encoding table: The bit strings have first bit in low bit.
  54.  * Note that counts were scaled so code fits unsigned integer. 
  55.  */
  56.  
  57. static int      codelen[NUMVALS];    /* number of bits in code */
  58. static unsigned short code[NUMVALS];    /* code itself, right adjusted */
  59. static unsigned short tcode;    /* temporary code value */
  60. static long     valcount[NUMVALS];    /* actual count of times seen */
  61.  
  62. /* Variables used by encoding process */
  63.  
  64. static int      curin;        /* value currently being encoded */
  65. static int      cbitsrem;    /* # of code string bits left */
  66. static unsigned short ccode;    /* current code right justified */
  67.  
  68. static    void    scale(), heap(), adjust(), bld_tree(), init_enc(), put_int();
  69. static    int    cmptrees(), buildenc(), maxchar();
  70. void 
  71. init_sq()
  72. {                /* prepare for scanning pass */
  73.     int             i;    /* node index */
  74.  
  75.     /*
  76.      * Initialize all nodes to single element binary trees with zero
  77.      * weight and depth. 
  78.      */
  79.  
  80.     for (i = 0; i < NUMNODES; ++i) {
  81.         node[i].weight = 0;
  82.         node[i].tdepth = 0;
  83.         node[i].lchild = NOCHILD;
  84.         node[i].rchild = NOCHILD;
  85.     }
  86.  
  87.     for (i = 0; i < NUMVALS; i++)
  88.         valcount[i] = 0;
  89. }
  90.  
  91. void 
  92. scan_sq(c)            /* add a byte to the tables */
  93.     int             c;    /* byte to add */
  94. {
  95.     unsigned short *wp;    /* speeds up weight counting */
  96.  
  97.     /* Build frequency info in tree */
  98.  
  99.     if (c == EOF)        /* it's traditional */
  100.         c = SPEOF;    /* dumb, but traditional */
  101.  
  102.     if (*(wp = &node[c].weight) != MAXCOUNT)
  103.         ++(*wp);    /* bump weight counter */
  104.  
  105.     valcount[c]++;        /* bump byte counter */
  106. }
  107.  
  108. long 
  109. pred_sq()
  110. {                /* predict size of squeezed file */
  111.     int             i;
  112.     int             btlist[NUMVALS];    /* list of intermediate
  113.                          * b-trees */
  114.     int             listlen;/* length of btlist */
  115.     unsigned short    ceiling;/* limit for scaling */
  116.     long            size = 0;    /* predicted size */
  117.     int             numnodes;    /* # of nodes in simplified tree */
  118.  
  119.     scan_sq(EOF);        /* signal end of input */
  120.  
  121.     ceiling = MAXCOUNT;
  122.  
  123.     /* Keep trying to scale and encode */
  124.  
  125.     do {
  126.         scale(ceiling);
  127.         ceiling /= 2;    /* in case we rescale */
  128.  
  129.         /*
  130.          * Build list of single node binary trees having leaves for
  131.          * the input values with non-zero counts 
  132.          */
  133.  
  134.         for (i = listlen = 0; i < NUMVALS; ++i) {
  135.             if (node[i].weight != 0) {
  136.                 node[i].tdepth = 0;
  137.                 btlist[listlen++] = i;
  138.             }
  139.         }
  140.  
  141.         /*
  142.          * Arrange list of trees into a heap with the entry indexing
  143.          * the node with the least weight at the top. 
  144.          */
  145.  
  146.         heap(btlist, listlen);
  147.  
  148.         /* Convert the list of trees to a single decoding tree */
  149.  
  150.         bld_tree(btlist, listlen);
  151.  
  152.         /* Initialize the encoding table */
  153.  
  154.         init_enc();
  155.  
  156.         /*
  157.          * Try to build encoding table. Fail if any code is > 16 bits
  158.          * long. 
  159.          */
  160.     } while (buildenc(0, dctreehd) == ERROR);
  161.  
  162.     /* Initialize encoding variables */
  163.  
  164.     cbitsrem = 0;        /* force initial read */
  165.     curin = 0;        /* anything but endfile */
  166.  
  167.     for (i = 0; i < NUMVALS; i++)    /* add bits for each code */
  168.         size += valcount[i] * codelen[i];
  169.  
  170.     size = (size + 7) / 8;    /* reduce to number of bytes */
  171.  
  172.     numnodes = dctreehd < NUMVALS ? 0 : dctreehd - (NUMVALS - 1);
  173.  
  174.     size += sizeof(short) + 2 * numnodes * sizeof(short);
  175.  
  176.     return size;
  177. }
  178.  
  179. /*
  180.  * The count of number of occurrances of each input value have already been
  181.  * prevented from exceeding MAXCOUNT. Now we must scale them so that their
  182.  * sum doesn't exceed ceiling and yet no non-zero count can become zero. This
  183.  * scaling prevents errors in the weights of the interior nodes of the
  184.  * Huffman tree and also ensures that the codes will fit in an unsigned
  185.  * integer. Rescaling is used if necessary to limit the code length. 
  186.  */
  187.  
  188. static    void
  189. scale(ceil)
  190.     unsigned short    ceil;    /* upper limit on total weight */
  191. {
  192.     register int    i;
  193.     int             ovflw, divisor;
  194.     unsigned short    w, sum;
  195.     unsigned char   increased;    /* flag */
  196.  
  197.     do {
  198.         for (i = sum = ovflw = 0; i < NUMVALS; ++i) {
  199.             if (node[i].weight > (ceil - sum))
  200.                 ++ovflw;
  201.             sum += node[i].weight;
  202.         }
  203.  
  204.         divisor = ovflw + 1;
  205.  
  206.         /* Ensure no non-zero values are lost */
  207.  
  208.         increased = FALSE;
  209.         for (i = 0; i < NUMVALS; ++i) {
  210.             w = node[i].weight;
  211.             if (w < divisor && w != 0) {    /* Don't fail to provide
  212.                              * a code if it's used
  213.                              * at all */
  214.  
  215.                 node[i].weight = divisor;
  216.                 increased = TRUE;
  217.             }
  218.         }
  219.     } while (increased);
  220.  
  221.     /* Scaling factor chosen, now scale */
  222.  
  223.     if (divisor > 1)
  224.         for (i = 0; i < NUMVALS; ++i)
  225.             node[i].weight /= divisor;
  226. }
  227.  
  228. /*
  229.  * heap() and adjust() maintain a list of binary trees as a heap with the top
  230.  * indexing the binary tree on the list which has the least weight or, in
  231.  * case of equal weights, least depth in its longest path. The depth part is
  232.  * not strictly necessary, but tends to avoid long codes which might provoke
  233.  * rescaling. 
  234.  */
  235.  
  236. static    void
  237. heap(list, length)
  238.     int             list[], length;
  239. {
  240.     register int    i;
  241.  
  242.     for (i = (length - 2) / 2; i >= 0; --i)
  243.         adjust(list, i, length - 1);
  244. }
  245.  
  246. /* Make a heap from a heap with a new top */
  247.  
  248. static    void
  249. adjust(list, top, bottom)
  250.     int             list[], top, bottom;
  251. {
  252.     register int    k, temp;
  253.  
  254.     k = 2 * top + 1;    /* left child of top */
  255.     temp = list[top];    /* remember root node of top tree */
  256.  
  257.     if (k <= bottom) {
  258.         if (k < bottom && cmptrees(list[k], list[k + 1]))
  259.             ++k;
  260.  
  261.         /* k indexes "smaller" child (in heap of trees) of top */
  262.         /* now make top index "smaller" of old top and smallest child */
  263.  
  264.         if (cmptrees(temp, list[k])) {
  265.             list[top] = list[k];
  266.             list[k] = temp;
  267.  
  268.             /* Make the changed list a heap */
  269.  
  270.             adjust(list, k, bottom);    /* recursive */
  271.         }
  272.     }
  273. }
  274.  
  275. /*
  276.  * Compare two trees, if a > b return true, else return false. Note
  277.  * comparison rules in previous comments. 
  278.  */
  279.  
  280. static    int 
  281. cmptrees(a, b)
  282.     int             a, b;    /* root nodes of trees */
  283. {
  284.     if (node[a].weight > node[b].weight)
  285.         return TRUE;
  286.     if (node[a].weight == node[b].weight)
  287.         if (node[a].tdepth > node[b].tdepth)
  288.             return TRUE;
  289.     return FALSE;
  290. }
  291.  
  292. /*
  293.  * HUFFMAN ALGORITHM: develops the single element trees into a single binary
  294.  * tree by forming subtrees rooted in interior nodes having weights equal to
  295.  * the sum of weights of all their descendents and having depth counts
  296.  * indicating the depth of their longest paths. 
  297.  *
  298.  * When all trees have been formed into a single tree satisfying the heap
  299.  * property (on weight, with depth as a tie breaker) then the binary code
  300.  * assigned to a leaf (value to be encoded) is then the series of left (0)
  301.  * and right (1) paths leading from the root to the leaf. Note that trees are
  302.  * removed from the heaped list by moving the last element over the top
  303.  * element and reheapin